// 剑指 Offer Problem Nr. 30: 包含 min 函数的栈

/*
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:
	MinStack minStack = new MinStack();
	minStack.push(-2);
	minStack.push(0);
	minStack.push(-3);
	minStack.min();   --> 返回 -3.
	minStack.pop();
	minStack.top();      --> 返回 0.
	minStack.min();   --> 返回 -2.

提示：
    各函数的调用总次数不超过 20000 次

注意：本题与主站 155 题相同：https://leetcode-cn.com/problems/min-stack/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import "math"

type MinStack struct {
	stack1 []int
	stack2 []int
}

func Constructor() MinStack {
	return MinStack{
		stack1: []int{},
		stack2: []int{math.MaxInt},
	}
}


func (ms *MinStack) Push(x int)  {
	ms.stack1 = append(ms.stack1, x)
	oldMin := ms.stack2[len(ms.stack2)-1]
	if x < oldMin {
		ms.stack2 = append(ms.stack2, x)
	} else {
		ms.stack2 = append(ms.stack2, oldMin)
	}
}


func (ms *MinStack) Pop()  {
	ms.stack1 = ms.stack1[:len(ms.stack1)-1]
	ms.stack2 = ms.stack2[:len(ms.stack2)-1]
}


func (ms *MinStack) Top() int {
	return ms.stack1[len(ms.stack1)-1]
}


func (ms *MinStack) Min() int {
	return ms.stack2[len(ms.stack2)-1]
}
